package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k. 
题目大意

	给定整数数组和整数k，找出数组中是否有两个不同的索引i和j，使得nums [i] = nums [j]，并且i和j之间的绝对差值最多为k。 
解题思路
	
 * @Date 2017-09-28 13：48
 */
public class _219_Contains_Duplicate_II {
	/**
	 * 暴力匹配：超时！！！
	 * @param nums
	 * @param k
	 * @return
	 */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
    	int N = nums.length;
    	for (int i = 0; i < N-1; i ++) {
    		for (int j = i+1; j < N; j ++) {
    			if (nums[i]==nums[j] && Math.abs(i-j)<=k)	{
    				return true;
    			}
    		}
    	}
        return false;
    }
    
    /**
     * 法二：使用hashMap处理
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate2(int[] nums, int k) {
    	int N = nums.length;
    	//K..元素, V..索引
    	HashMap<Integer, Integer> map = new HashMap<>();
    	for (int i = 0; i < N; i ++) {
    		int ele = nums[i];
    		if (map.containsKey(ele) 
    				&&	(Math.abs(map.get(ele) - i)<=k)) {
    			return true;
    		} else {
    			map.put(ele, i);
    		}
    	}
        return false;
    }
	public static void main(String[] args) {
		_219_Contains_Duplicate_II obj = new _219_Contains_Duplicate_II();
		obj.containsNearbyDuplicate2(new int[]{4, 2, 4, 3, 1, 4, 5}, 2);
	}

}
